package abs.syn;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;

import util.StringUtil;

public class Parse {
	public List<Dependency> dependencies = null;
	public SynTree root = null;
	public List<SynTree> leaves = null;
	public String originalLine = null, processedLine = null;
	// words after processing
	public String[] words = null, originalWords = null;
	// positions of original words in the original sentence
	public int[] origStartPos = null, origEndPos = null;
	// processed words mapped back to positions of the orig sent
	public int[] startPos = null, endPos = null;
	// <wordIdx, List<Dep> >
	public Hashtable<Integer, List<Dependency>> wordToDeps = new Hashtable<Integer, List<Dependency>>();


	public Parse(String line, SynTree sentStart, List<Dependency> deps){
		originalLine = line;
		root = sentStart;
		dependencies = deps;

		// build up the rest of variables
		build();
	}

	/**
	 * // build up the rest of variables
	 */
	private void build(){
		//		System.err.println("building parse");
		// leaves
		LinkedList<SynTree> stack = new LinkedList<SynTree>();
		leaves = new ArrayList<SynTree>();
		stack.add(root);
		while(!stack.isEmpty()){
			SynTree cur = stack.removeLast();
			if (cur.isLeaf()){
				leaves.add(cur);
			}
			else{

				for (int i=cur.children.size()-1; i > -1 ; i--)
					stack.add(cur.children.get(i));
			}
		}
		// words 
		words = new String[leaves.size()];
		processedLine = "";
		for (int i = 0; i < leaves.size(); i++){
			words[i] = leaves.get(i).getName();
			processedLine +=words[i] +" ";
		}
		processedLine = processedLine.trim();
		originalWords = originalLine.split(" ");


		// fix the positions FIXME could be wrong though
		if (words.length==originalWords.length){
			// trivial case
			origStartPos = new int[originalWords.length];
			origEndPos = new int[originalWords.length];
			startPos = new int[words.length];
			endPos = new int[words.length];
			int cur = 0;
			for (int i = 0; i < words.length; i++){
				origStartPos[i] = cur;
				startPos[i] = cur;
				origEndPos[i] = cur+originalWords[i].length();
				endPos[i] = cur+originalWords[i].length();
				cur += originalWords[i].length()+1;
			}
		}
		else{
			//			System.err.println("matching positions");
			// something got splitted
			origStartPos = new int[originalWords.length];
			origEndPos = new int[originalWords.length];
			startPos = new int[words.length];
			endPos = new int[words.length];
			int cur = 0;
			for (int i = 0; i < originalWords.length; i++){
				origStartPos[i] = cur;
				origEndPos[i] = cur+originalWords[i].length();
				cur +=originalWords[i].length()+1;
			}
			int idxOrig = 0;
			int prevStop = 0;// if prevStop!=0, then last word hasn't been fully matched yet.
			for (int i = 0; i < words.length; i++){
				String tmpWord = pennConvert(words[i]);
				if (prevStop==0){
					if (idxOrig >= originalWords.length){
						System.err.println("[PARSE_BUILD] "+tmpWord + "@"+i+" with"+StringUtil.concatenateStringArray(words, "::") + "   --  "+idxOrig+"@"+StringUtil.concatenateStringArray(originalWords, ",, "));
					}
					if (tmpWord.equals(originalWords[idxOrig])){
						startPos[i] = origStartPos[idxOrig];
						endPos[i] = origEndPos[idxOrig];
						idxOrig ++;
					}
					else if (originalWords[idxOrig].startsWith(tmpWord)){
						startPos[i] = origStartPos[idxOrig];
						endPos[i] = startPos[i] + tmpWord.length();
						prevStop = tmpWord.length();
					}
					else{
						// originalWord has "\n" as the first char?
						System.err.println("[PARSE]prevStop = 0 originalWord = "+originalWords[idxOrig]+" @ "+idxOrig+", "+ tmpWord +":"+words[i]+"@"+i);
						startPos = null;
						endPos = null;
						break;
					}
				}
				else{
					if (tmpWord.equals(originalWords[idxOrig].substring(prevStop))){
						startPos[i] = endPos[i-1];
						endPos[i] = origEndPos[idxOrig];
						prevStop = 0;
						idxOrig ++;
					}
					else if (originalWords[idxOrig].substring(prevStop).startsWith(tmpWord)){
						startPos[i] = endPos[i-1];
						endPos[i] = startPos[i] + tmpWord.length();
						prevStop += tmpWord.length();
					}
					else{
						System.err.println("prevStop = 0 originalWord = "+originalWords[idxOrig]+" @ "+idxOrig+", "+ tmpWord +":"+words[i]+"@"+i);
					}
				}
			}
		}

		// build Hashtable for <word, list<dep>>
		//		System.err.println("building dep graphs");
		if (dependencies != null){
			for (int i = 0; i < words.length; i++){
				this.wordToDeps.put(i, new ArrayList<Dependency>());
			}
			try{
				for (Dependency dep: dependencies){
					wordToDeps.get(dep.govIdx-1).add(dep);
					wordToDeps.get(dep.depIdx-1).add(dep);
				}
			}catch(Exception e){
				System.out.println(dependencies);
				System.out.println(words.length);
				System.out.println(originalLine);
				System.out.println(processedLine);

				e.printStackTrace();
				System.exit(-1);
			}
		}
	}
	private String pennConvert(String string) {
		if (string.equals("-LRB-")){
			return "(";
		}else if (string.equals("-LSB-")){
			return "[";
		}else if (string.equals("-LCB-")){
			return "{";
		}else if (string.equals("-RRB-")){
			return ")";
		}else if (string.equals("-RSB-")){
			return "]";
		}else if (string.equals("-RCB-")){
			return "}";
		}else if (string.equals("``")){
			return "\"";
		}else if (string.equals("''")){
			return "\"";
			//		}else if (string.equals("...")){

		}else {
			return string;	
		}

	}

	/** 
	 * idx of two words
	 * @param from
	 * @param to
	 * @return
	 */
	public List<DependencyPath> getDependencyPath(int from, int to){
		ArrayList<Integer> governors = new ArrayList<Integer>(), dependents = new ArrayList<Integer>();
		governors.add(from);
		dependents.add(to);

		LinkedList<DependencyPath> res = new LinkedList<DependencyPath>();
		if (governors.size()==1&& dependents.size()==1 && governors.get(0)==dependents.get(0)){
			DependencyPath dp  =new DependencyPath();
			Dependency d = new Dependency();
			d.name = "SAMEWORD";
			dp.deps.add(d);
			dp.isLeftArgument.add(true);
			res.add(dp);
		}else{
			// for each searchable word in 1
			// 			for each searchable word in 2
			// 				find path between them
			//				keep track of all possible paths
			// 				stop when self-loop emerges
			for (Integer src: governors){
				for (Integer dst: dependents){
					LinkedList<DependencyPath> curList = new LinkedList<DependencyPath>();
					//				LinkedList<HashSet<Integer>> visited = new LinkedList<HashSet<Integer>>();
					findPath(src, dst, new DependencyPath(), new HashSet<Integer>(), curList);
					res.addAll(curList);
				}
			}
		}
		return res;
	}

	/**
	 * can return multiple <code>DependencyPath</code>s
	 * @param startpos1
	 * @param endpos1
	 * @param startpos2
	 * @param endpos2
	 * @return
	 */
	public List<DependencyPath> getDependencyPath(int startpos1, int endpos1, int startpos2, int endpos2){
		// find all the words
		// TODO notice that pos could be in the middle of a hyphenated word
		ArrayList<Integer> governors = new ArrayList<Integer>(), dependents = new ArrayList<Integer>();
		for (int  i= 0; i < words.length; i++){
			//			System.out.println("["+i+"]" + startPos[i]+", "+endPos[i]);
			if (startPos[i] >=startpos1 && endPos[i] <=endpos1 || startPos[i] <=startpos1 && endPos[i] >=endpos1){
				governors.add(i);
			}
			if (startPos[i] >=startpos2 && endPos[i] <=endpos2 || startPos[i] <=startpos2 && endPos[i] >=endpos2){
				dependents.add(i);
			}
		}

		//				System.err.println("gov:"+governors +", dep:"+dependents);
		// see if some words that only have dep to other words within the span
		// drop them in the search
		HashSet<Integer> toRemove = new HashSet<Integer>();
		if (governors.size()!=1){
			for (int i = 0; i< governors.size(); i++){
				List<Dependency> list = wordToDeps.get(i);
				if (list.size() == 1&& governors.contains(list.get(0).depIdx-1)){
					toRemove.add(i);
				}
			}
		}
		for (Integer idx: toRemove){
			governors.remove(idx);
		}
		toRemove.clear();
		if (dependents.size()!=1){
			for (int i = 0; i< dependents.size(); i++){
				List<Dependency> list = wordToDeps.get(i);
				if (list.size() == 1&& dependents.contains(list.get(0).govIdx-1)){
					toRemove.add(i);
				}
				//			System.out.println(words[dependents.get(i)]);
			}
		}
		for (Integer idx: toRemove){
			dependents.remove(idx);
		}
		//		System.out.println("gov:"+governors +", dep:"+dependents);

		LinkedList<DependencyPath> res = new LinkedList<DependencyPath>();
		if (governors.size()==1&& dependents.size()==1 && governors.get(0)==dependents.get(0)){
			if (endpos1 +1 == startpos2 && originalLine.charAt(endpos1)=='-'){
				DependencyPath dp  =new DependencyPath();
				Dependency d = new Dependency();
				d.name = "HYPHEN";
				d.govIdx =  governors.get(0)+1;
				d.depIdx =  governors.get(0)+1;
				d.gov = originalLine.substring(startpos1, endpos1);
				d.dep = originalLine.substring(startpos2, endpos2);
				dp.deps.add(d);
				dp.isLeftArgument.add(true);
				res.add(dp);
			}else if (endpos2 +1 == startpos1 && originalLine.charAt(endpos2)=='-'){
				DependencyPath dp  =new DependencyPath();
				Dependency d = new Dependency();
				d.name = "HYPHEN";
				d.govIdx =  governors.get(0)+1;
				d.depIdx =  governors.get(0)+1;
				d.gov = originalLine.substring(startpos2, endpos2);
				d.dep = originalLine.substring(startpos1, endpos1);
				dp.deps.add(d);
				dp.isLeftArgument.add(false);
				res.add(dp);
			}
		}else{
			// for each searchable word in 1
			// 			for each searchable word in 2
			// 				find path between them
			//				keep track of all possible paths
			// 				stop when self-loop emerges
			for (Integer src: governors){
				for (Integer dst: dependents){
					LinkedList<DependencyPath> curList = new LinkedList<DependencyPath>();
					//				LinkedList<HashSet<Integer>> visited = new LinkedList<HashSet<Integer>>();
					findPath(src, dst, new DependencyPath(), new HashSet<Integer>(), curList);
					res.addAll(curList);
				}
			}
		}

		return res;
	}

	public DependencyPath getShortestPath(int from, int to){
		List<DependencyPath> list = 
			getDependencyPath(from, to);
		DependencyPath pp = null;
		if(!list.isEmpty()){
			int length = 100;
			for (DependencyPath dp: list){
				if (dp.deps.size() < length){
					length = dp.deps.size();
					pp = dp;
				}
			}
		}
		return pp;
	}


	public DependencyPath getShortestPath(int startpos1, int endpos1, int startpos2, int endpos2){
		List<DependencyPath> list = 
			getDependencyPath(startpos1, endpos1, startpos2, endpos2);
		DependencyPath pp = null;
		if(!list.isEmpty()){
			int length = 100;
			for (DependencyPath dp: list){
				if (dp.deps.size() < length){
					length = dp.deps.size();
					pp = dp;
				}
			}
		}
		return pp;
	}

	private void findPath(Integer src, Integer dst, DependencyPath cur, HashSet<Integer> visited,
			LinkedList<DependencyPath> curList) {
		if (src!=dst){
			if (visited.contains(src)){
				//				System.err.println("[LOOP return]"+cur+"  "+visited+"  "+src+"   "+dst);
				// loop emerges
				cur.removeLast();
				return;
			}
			else{

				visited.add(src);
				//				boolean tried = false;
				if (wordToDeps.containsKey(src)){
					for (Dependency dep: wordToDeps.get(src)){
						if (cur.contains(dep))
							continue;
						//					tried = true;
						//					System.err.println("[Searching "+dep+"]"+cur+"  "+visited+"  "+src+"   "+dst);
						if (dep.govIdx-1 == src){
							cur.insert(dep, true);
							//						visited.add(src);
							findPath(dep.depIdx-1, dst, cur, visited,curList);
						}
						else if (dep.depIdx -1 ==src){
							cur.insert(dep, false);
							//						visited.add(src);
							findPath(dep.govIdx-1, dst, cur, visited,curList);
						}
						else{
							System.err.println("findPath@Parse: find dep err");
						}
					}
				}
				/*if(tried)*/
				if(!cur.deps.isEmpty()){
					visited.remove(src);
					cur.removeLast();
				}
			}
		}
		else{
			// found one
			//			System.err.println("[Found]"+cur+"  "+visited+"  "+src+"   "+dst);
			if (cur.deps.size() != 0){
				curList.add((DependencyPath)cur.clone());
				cur.removeLast();
			}
			return;
		}
	}

	/**
	 * get the index of the head of the phrase containing <code>word</code>
	 * @param word
	 * @return
	 */
	public int getHead(int word){
		SynTree parent = this.leaves.get(word).parent;
		// FIXME is endsWith(P) enough ? or we need VP, NP, PP
		int limit = 0;
		while (!parent.getName().endsWith("P")){
			parent = parent.parent;
			limit++;
			if (limit > 2)
				break;
		}
		if (parent == null || parent.parent == null || parent.getName() == null || parent.parent.getName() == null){
			System.err.println("[DELETEME] "+leaves);
		}
		else
		{
			// if VP has a parent VP, etc
			while (parent.getName().equals(parent.parent.getName())){
				parent = parent.parent;

			}
		}
		return leaves.indexOf(getHead(parent));
	}

	/**
	 * 
	 * @param phrase
	 * @return
	 */
	public SynTree getHead(SynTree phrase){
		if (phrase == null) return null;
		SynTree parent = phrase;
		SynTree head = null;
		if (parent.getName().equals("VP")){

			// leftmost VB*
			ArrayList<SynTree> list = getLeaves(parent);
			for (int i = 0; i < list.size(); i++){
				if (list.get(i).parent.getName().startsWith("VB")){
					head = list.get(i);
					break;
				}
			}
			// leftmost VP FIXME it's not gonna happen, VP can't be leaf name
			if (head==null){
				for (int i = 0; i < parent.children.size(); i++){
					if (parent.children.get(i).getName().equals("VP")){
						head = getHead(parent.children.get(i));
						break;
					}
				}
			}
			// leftmost child
			if (head==null){
				head = list.get(0);
			}
		}
		else if (parent.getName().equals("NP")){
			// leftmost NP FIXME same as leftmost VP
			for (int i = 0; i < parent.children.size(); i++){
				if (parent.children.get(i).getName().equals("NP")){
					head = getHead(parent.children.get(i));
					break;
				}
			}
			// rightmost N*
			ArrayList<SynTree> list = getLeaves(parent);
			if (head==null){
				for (int i =0; i < list.size(); i++){
					if (list.get(i).parent.getName().startsWith("N")){
						head = list.get(i);
						break;
					}
				}
			}
			// rightmost JJ
			if (head==null){
				for (int i = list.size() - 1; i > -1 ; i--){
					if (list.get(i).parent.getName().equals("JJ")){
						head = list.get(i);
						break;
					}
				}
			}
			// right child
			if (head ==null){
				head = list.get(list.size()-1);
			}
		}
		else{

		}
		return head;
	}

	/**
	 * given a phrase, get the list of all leaves
	 * @param phrase
	 * @return
	 */
	public ArrayList<SynTree> getLeaves(SynTree phrase){
		ArrayList<SynTree> list = new ArrayList<SynTree>();
		LinkedList<SynTree> stack = new LinkedList<SynTree>();
		stack.add(phrase);
		while (!stack.isEmpty()){
			SynTree cur = stack.remove(0);
			if (cur.isLeaf()){
				list.add(cur);
			}
			else{
				stack.addAll(0, cur.children);
			}
		}
		return list;
	}

	public int getWord(int pos) {
		int idx = -1;
		for (int i = 0; i < leaves.size(); i++){
			if (this.startPos[i] <= pos && pos <= this.endPos[i]){
				idx = i;
				break;
			}
		}
		return idx;
	}
}
